1 Field of the Invention
The present invention pertains to the multiplexing of multiplexed packets into carrying packets, such as (for example) the multiplexing of AAL2 packets into ATM cells.
2. Related Art and Other Considerations
Packet multiplexing protocols typically multiplex a packet of a given type (multiplexed packet) into one or more packets of another type (carrying packets). An example of a multiplexing protocol can be AAL2 (ATM Adaptation Layer 2), whose variable-sized packets can be multiplexed into fixed sized ATM cells (ATM cells being the carrying packets). This particular example is described in ITU-T, AAL2 Type 2 Signalling Protocol (Capability Set 1), New ITU-T Recommendation Q.2630.1, December 1999), which is incorporated herein by reference in its entirety. See also U.S. patent application Ser. No. 09/188,102, entitled “ASYNCHRONOUS TRANSFER MODE SYSTEM HANDLING DIFFERING AAL PROTOCOLS,” which is also incorporated herein by reference in its entirety.
For fixed-sized carrying cells, one objective in performing the multiplexing is that the unused payload of a carrying packet should be minimized, i.e., the multiplexer should send out a carrying packet (e.g., an ATM cell in the foregoing example illustration) with as full a payload as possible (most preferably with a full payload). For carrying packets of variable size, the objective is instead to maximize transmission efficiency by multiplexing as many multiplexed packets as possible into a carrying packet. Yet for both type carrying packets there is also the essentially contradictory objective that packet delay on the link transmitting the carrying cells should be minimized. This second objective encourages the multiplexer to send out a carrying packet as early as possible (e.g., without having to wait unduly for the payload to be filled with user data) or for more multiplexed packets to be included.
Multiplexed packets from different sources (different connections) are distinguished by connection identifiers (CIDs). Since the CIDs are coded with a predetermined (and typically standardized) number of bits, the number of connections that can be distinguished by the CIDs is limited in accordance with the number of bits so allotted for the coding. For example, for AAL2 at most two hundred forty eight (248) connections can be multiplexed onto one ATM VC (Virtual Channel), the virtual channel being identified by a VCI (Virtual Channel Identifier).
FIG. 4 illustrates a typical state of the art protocol multiplexing situation in which a maximum of two hundred forty eight (248) AAL2 connections can be multiplexed into an ATM VC. In FIG. 4, AAL2 packets from connections conn1 through conn248 are multiplexed into ATM cells for output on a channel identified as VC 400. The ATM channel VC 400 has a capacity of CVC (cells/sec). Upon arrival, the packets from connections conn1 through conn248 (having respective connection identifiers CID1 through CID248) are stored in queue 402. Queue 402 is an AAL2 level queue for VC 400. An AAL2 multiplexer 404 multiplexes the AAL2 packets stored in queue 402 into an output buffer 406 for ATM channel VC 400.
In an attempt both to optimize the delay and the unused payload of the carrying packet, state of the art protocol multiplexing systems such as that shown in FIG. 4 usually have a single timer 408. When an ATM cell (e.g., carrier cell) cannot be fully filled by multiplexer 404, the timer 408 starts counting down from a predetermined maximum value (e.g., 1 millisecond).
If the ATM cell can be filled before timer 408 expires, the filled ATM cell is sent out on the VC. The timer 408 is then restarted for the next outgoing ATM cell on the VC. But if the ATM cell cannot be filled before timer 408 expires, the partially-filled ATM cell is sent to ATM output buffer 406 (thereby limiting the delay). The timer 408 is then restarted if a carrying packet (e.g., ATM cell) cannot be filled by multiplexer 404, and queue 402 is devoid of any multiplexed packets (AAL2 packets) for the next outgoing ATM cell from the multiplexer 404. By tuning this maximum timer value it is possible to achieve a compromise between the duration of the multiplexing procedure and unused ATM payload.
In many cases it would be advantageous to have a larger number of connections involved in the multiplexing (e.g., a larger than conventional number of CIDs). The advantage is related to the fact that multiplexing more connections over a larger resource increases multiplexing efficiency. But to multiplex more AAL2 connections, for example, there must be more multiplexers identified by different virtual channel identifiers (VCIs). A simplified approach in this regard would be to construct a large FIFO queue from many CID limited (e.g., small) FIFO queues, but in a manner to keep packets of differing AAL2 connections, which are associated with different VCIs, from being multiplexed into the same ATM cell (keeping in mind that an ATM cell should carry only packets of AAL2 connections multiplexed wihtin one VC).
FIG. 5 illustrates how state of the art timer mechanisms for protocol multiplexing are problematic (at least from a delay perspective) when multiplexing with a larger than conventional number of connections (e.g., CIDs). The multiplexing protocol system of FIG. 5 outputs ATM cells onto a virtual path VP 500. The ATM VP has a capacity of CVP (cells/sec). In FIG. 5, k number of AAL2 level queues 502 are provided, e.g., queue 502, through queue 502k. Queue 502, is an AAL2 level queue for VC(1); queue 5022 is an AAL2 level queue for VC 2; and so forth up to queue 502k which is an AAL2 level queue for VC(k). Upon arrival at a node having the multiplexing system, the packets from connections conn1 through conn248 for VC(1) (having respective connection identifiers CID1 through CID248) are stored in queue 5021; the packets from connections conn1 through conn248 for VC(k) (having respective connection identifiers CID1 through CID248) are stored in queue 502k; and so forth. The multiplexer 5041 multiplexes AAL2 packets stored in queue 5021 (for VC(1)) into an output buffer 506 for ATM VP 500 when an ATM cell for VC(1)is being assembled in output buffer 506. Likewise, multiplexer 504k multiplexes AAL2 packets stored in queue 502k (for VC(k)) into output buffer 506 for ATM VP 500 when an ATM cell for VC(k) is being assembled in output buffer 506. In the FIG. 5 system, each multiplexer 504 has an associated timer 508 (e.g., multiplexer 5041 has timer 5081; multiplexer 504k has timer 508k; and so forth).
Thus, in the example scenario of FIG. 5, k number of VCs are multiplexed into a virtual path (VP 500) of capacity CVP. In the particular example situation shown in the FIG. 5 scenario, a packet which would fill about 3.25 ATM cells arrived at multiplexer 5041. Since the packet can fully fill three ATM cells in output buffer 506, three ATM cells from multiplexer 5041 are stored in output buffer 506 as indicated by the dotted cells in FIG. 5. But since the packet arriving at multiplexer 5041 could only partially fill a fourth ATM cell, the remaining packet contents (e.g., the packet contents not corresponding to the three ATM cells stored in output buffer 506) are not yet stored in output buffer 506. Rather, according to the state of the art practice, timer 5081 is started. While timer 5081 is counting down, another packet arrives to multiplexer 504k (belonging to VC(k)). The packet which arrives at multiplexer 504k fully fills four ATM cells in output buffer 506, as indicated by the cross hatched cells in FIG. 5. When timer 5081 subsequently expires, the last segment of the packet which previously arrived at multiplexer 5041 is stored in a separate ATM cell in output buffer 506. The consequence of this is, that even if originally the dotted packet arrived earlier than the cross hatched packet, the dotted packet will be sent out from the multiplexing system later than the cross hatched packet. Thus, the first-in-first-out principle is violated.
In the example situation of FIG. 5, from the perspective of the output buffer 506 the last segment from multiplexer 5041 was overtaken by four cells formed from the packet which arrived at multiplexer 504k. Such a lag (of four ATM cells for VC(k)) between the fourth ATM cell associated with VC(1) and the earlier three ATM cells for VC(1) creates additional delay, because all four cells from multiplexer 504k must be served before the last segment of the packet applied to multiplexer 5041 can be served.
What is needed therefore, and an object of the present invention, are techniques for better balancing delay and payload optimization in a packet multiplexing protocol system.